package com.wenhai.liuyubobobo.imooc.sort;

import java.util.Arrays;
import java.util.Random;

import static com.wenhai.liuyubobobo.imooc.sort.SelectionSort.*;

/**
 * 快速排序
 *
 * @author wenhai
 * @date   2021/2/24
 */
public class QuickSort {
    private static final Random RANDOM = new Random();
    private QuickSort(){

    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }
    public static <E extends Comparable<E>> void sort2(E[] arr) {
        sort2(arr, 0, arr.length - 1);
    }
    public static <E extends Comparable<E>> void sort2ways(E[] arr) {
        sort2ways(arr, 0, arr.length - 1);
    }
    public static <E extends Comparable<E>> void sort3ways(E[] arr) {
        sort3ways(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r){
        if (r - l <= 15) {
            InsertionSort.sort(arr, l, r);
            return;
        }
        int index = partition(arr, l, r);
        sort(arr, l, index);
        sort(arr, index + 1, r);
    }
    private static <E extends Comparable<E>> void sort2ways(E[] arr, int l, int r){
        if (l >= r) {
            return;
        }
        int index = partition2(arr, l, r);
        sort2ways(arr, l, index - 1);
        sort2ways(arr, index + 1, r);
    }
    private static <E extends Comparable<E>> void sort3ways(E[] arr, int l, int r){
        if (l >= r) {
            return;
        }
        int p = l + RANDOM.nextInt(r - l + 1);
        swap(arr, l, p);
        int lt = l;
        int gt = r + 1;
        int i  = l + 1;
        while (i < gt) {
            if (arr[i].compareTo(arr[l]) < 0) {
                lt++;
                swap(arr, i, lt);
                i++;
            } else if (arr[i].compareTo(arr[l]) > 0) {
                gt--;
                swap(arr, i, gt);
            } else {
                i++;
            }
        }
        swap(arr, l, lt);
        sort3ways(arr, l, lt - 1);
        sort3ways(arr, gt, r);

    }

    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r) {
        int p = l + RANDOM.nextInt(r - l + 1);
        swap(arr, l, p);
        int lt = l;
        for (int j = l + 1; j <= r; j++) {
            if (arr[j].compareTo(arr[l]) < 0) {
                lt++;
                if (lt != j) {
                    swap(arr, lt, j);

                }
            }
        }
        if (lt != l) {
            swap(arr, lt, l);
        }
        return lt;
    }
    private static <E extends Comparable<E>> int partition2(E[] arr, int l, int r) {
        int p = l + RANDOM.nextInt(r - l + 1);
        swap(arr, l, p);
        int i = l + 1;
        int j = r;
        while (true) {
            while (i <= j && arr[i].compareTo(arr[l]) < 0) {
                i++;
            }
            while (j >= i && arr[i].compareTo(arr[l]) > 0) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;
    }
    private static <E extends Comparable<E>> void sort2(E[] arr, int l, int r){
        if (r - l <= 15) {
            InsertionSort.sort(arr, l, r);
            return;
        }
        int index = partition(arr, l, r);
        sort2(arr, l, index - 1);
        sort2(arr, index + 1, r);
    }

    public static void main(String[] args) {
        int[] dataSize = {10000000};
        for (int size : dataSize) {
            Integer[] arr = ArrayGenerator.generateRandomArray(size, 1);
            Integer[] arr2 = Arrays.copyOf(arr, arr.length);
            Integer[] arr3 = Arrays.copyOf(arr, arr.length);
//            SortingHelper.sortTest("QuickSort", QuickSort::sort2, arr);
            SortingHelper.sortTest("QuickSort2ways", QuickSort::sort2ways, arr2);
            SortingHelper.sortTest("QuickSort3ways", QuickSort::sort3ways, arr3);
        }
    }
}
